%!TEX program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[10pt,a4paper]{article} 

\usepackage{ctex} % 中文支持
\usepackage[top=2.5cm, bottom=2.5cm, left=2.5cm, right=2.5cm]{geometry} % 页边距
\usepackage{amsmath, amssymb} % 数学公式与符号
\usepackage{graphicx}

\usepackage{pythonhighlight}
\usepackage{url} 

\usepackage{tikz}
\usetikzlibrary{graphs,arrows.meta}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 使表格美观
\usepackage{array}
\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
%\newcolumntype{N}{@{}m{0pt}@{}}
\setlength\extrarowheight{3pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{titling}
\setlength{\droptitle}{-2cm} % 标题上移

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%文档的题目、作者与日期
\author{221330100 WLQ }
\title{图论模型习题}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

%\begin{abstract}
%练习
%\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setcounter{tocdepth}{2}
%\renewcommand\contentsname{目录}
%
%\renewcommand {\baselinestretch} {1.3}\normalsize 
%\tableofcontents 
%\renewcommand {\baselinestretch} {1.0}\normalsize


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\section{}
\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item  写出下列无向图的邻接矩阵。

\begin{center}
\begin{tikzpicture}[auto]

%\node [circle,draw] (s7) at (0,0) {7}; 
\node [circle,draw] (s5) at (6,0) {5}; 
\node [circle,draw] (s6) at (0,0) {6}; 
\node [circle,draw] (s2) at (6,-2) {2}; 
\node [circle,draw] (s1) at (6,-3.5) {1}; 
\node [circle,draw] (s4) at (0,-3) {4}; 
\node [circle,draw] (s3) at (4,-4) {3}; 
\node [circle,draw] (s7) at (0,-5) {7}; 

\draw (s7) to node {} node [swap]{2} (s3);
\draw (s7) to node {3} node [swap]{} (s4);
\draw (s3) to node {2} node [swap]{} (s4);
\draw (s3) to node {2} node [swap]{} (s2);
\draw (s1) to node {1} node [swap]{} (s2);
\draw (s3) to node {} node [swap]{1} (s1);
\draw (s2) to node {3} node [swap]{} (s5);
\draw (s4) to node {3} node [swap]{} (s6);
\draw (s3) to node {4} node [swap]{} (s6);
\draw (s5) to node {4} node [swap]{} (s6);
\draw (s2) to node {5} node [swap]{} (s6);

\end{tikzpicture}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{0.5cm}
解答：



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\item  解释Dijkstra算法在下述例子中的前三步(a-b-c)的计算细节。 

\begin{center}
\includegraphics [height=10cm, width=14cm]{rosen-dijkstra-example.jpg}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{0.5cm}
解答：


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\item  某台机器可以连续工作4年，也可以在年末卖掉，换一台新的。
已知于各年初购置一台新机器的价格及不同使用年龄的机器在年末的处理价格如表所示。
又新机器第一年运行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8万、1.5万、2.0万元。
试确定该机器的最优更新策略，使得4年内用于更换、购买、及其运行维修的总费用最小。

\begin{table}[ht]
\centering
\caption{机器的购置价格与处理价格}\vspace{0.3cm}
\begin{tabular}{|M{4cm}|M{1.5cm}|M{1.5cm}|M{1.5cm}|M{1.5cm}|} \hline 
使用年份&1&2&3&4 \\ \hline 
年初购置价(万元) &2.5 & 2.6 & 2.8 & 3.1   \\ \hline 
旧机器价格(万元)  &2.0 & 1.6 & 1.3 & 1.1   \\ \hline 
\end{tabular}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{0.5cm}
解答：


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

